package com.leetcode.stackandqueue.demo6;

import java.util.*;

/**
 * @Author Zan
 * @Create 2024/7/18 20:50
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/sliding-window-maximum/description/  滑动窗口最大值
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {1, -1};
        int k = 1;
        Solution solution = new Solution();
        int[] ints = solution.maxSlidingWindow(arr, k);
        System.out.println(ints);
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int i = 0;
        int[] result = new int[nums.length - k + 1];
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            queue.add(num);
            if (queue.size() >= k) {
                Integer poll = queue.poll();
                result[i++] = max;
                if (poll > max) {
                    max = poll;
                }
            }
        }
        return result;
    }
}

class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}